//完全背包 采用二进制优化转化为01背包
#include <iostream>

using namespace std;
const int MAXN=30;
const int MAXM=200;

int n,m;
int w[MAXN+1],c[MAXN+1];
int maxc[MAXM+1];//maxc[v]容量为v取得的最大价值

int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>c[i];

    for(int i=1;i<=n;i++) //将第i个物品分解为重量是2^0*w[i],2^1*w[i],...2^k*w[i]的物品（2^k*w[i]<=m)
        for(int k=0,p=1;p*w[i]<=m;k++,p=1<<k){
            for(int v=m;v>=p*w[i];v--)
               //maxc[v]=max(maxc[v],maxc[v-p*w[i]]+p*c[i]);
               if (maxc[v-p*w[i]]+p*c[i]>maxc[v]) maxc[v]=maxc[v-p*w[i]]+p*c[i];
        }
    cout<<maxc[m];
}
